Search results for "Databases"
showing 10 items of 937 documents
RTIndeX: Exploiting Hardware-Accelerated GPU Raytracing for Database Indexing
2023
Data management on GPUs has become increasingly relevant due to a tremendous rise in processing power and available GPU memory. Just like in the CPU world, there is a need for performant GPU-resident index structures to speed up query processing. Unfortunately, mapping indexes efficiently to the highly parallel and hard-to-program hardware is challenging and often fails to yield the desired performance and flexibility. Therefore, we advocate to take a different route. Instead of proposing yet another hand-tailored index, we investigate whether we can exploit an indexing mechanism that is already built into modern GPUs: The raytracing hardware accelerator provided by NVIDIA RTX cards. To do …
Neural Networks, Inside Out: Solving for Inputs Given Parameters (A Preliminary Investigation)
2021
Artificial neural network (ANN) is a supervised learning algorithm, where parameters are learned by several back-and-forth iterations of passing the inputs through the network, comparing the output with the expected labels, and correcting the parameters. Inspired by a recent work of Boer and Kramer (2020), we investigate a different problem: Suppose an observer can view how the ANN parameters evolve over many iterations, but the dataset is oblivious to him. For instance, this can be an adversary eavesdropping on a multi-party computation of an ANN parameters (where intermediate parameters are leaked). Can he form a system of equations, and solve it to recover the dataset?
Graphical model inference : Sequential Monte Carlo meets deterministic approximations
2019
Approximate inference in probabilistic graphical models (PGMs) can be grouped into deterministic methods and Monte-Carlo-based methods. The former can often provide accurate and rapid inferences, but are typically associated with biases that are hard to quantify. The latter enjoy asymptotic consistency, but can suffer from high computational costs. In this paper we present a way of bridging the gap between deterministic and stochastic inference. Specifically, we suggest an efficient sequential Monte Carlo (SMC) algorithm for PGMs which can leverage the output from deterministic inference methods. While generally applicable, we show explicitly how this can be done with loopy belief propagati…
Finding k -dissimilar paths with minimum collective length
2018
Shortest path computation is a fundamental problem in road networks. However, in many real-world scenarios, determining solely the shortest path is not enough. In this paper, we study the problem of finding k-Dissimilar Paths with Minimum Collective Length (kDPwML), which aims at computing a set of paths from a source s to a target t such that all paths are pairwise dissimilar by at least \theta and the sum of the path lengths is minimal. We introduce an exact algorithm for the kDPwML problem, which iterates over all possible s-t paths while employing two pruning techniques to reduce the prohibitively expensive computational cost. To achieve scalability, we also define the much smaller set …
Multi-scale analysis of the European airspace using network community detection
2014
We show that the European airspace can be represented as a multi-scale traffic network whose nodes are airports, sectors, or navigation points and links are defined and weighted according to the traffic of flights between the nodes. By using a unique database of the air traffic in the European airspace, we investigate the architecture of these networks with a special emphasis on their community structure. We propose that unsupervised network community detection algorithms can be used to monitor the current use of the airspaces and improve it by guiding the design of new ones. Specifically, we compare the performance of three community detection algorithms, also by using a null model which t…
Open Data Quality Evaluation: A Comparative Analysis of Open Data in Latvia
2020
Nowadays open data is entering the mainstream - it is free available for every stakeholder and is often used in business decision-making. It is important to be sure data is trustable and error-free as its quality problems can lead to huge losses. The research discusses how (open) data quality could be assessed. It also covers main points which should be considered developing a data quality management solution. One specific approach is applied to several Latvian open data sets. The research provides a step-by-step open data sets analysis guide and summarizes its results. It is also shown there could exist differences in data quality depending on data supplier (centralized and decentralized d…
Exact quantum algorithms have advantage for almost all Boolean functions
2014
It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.
Application of LEAN Principles to Improve Business Processes: a Case Study in a Latvian IT Company
2020
The research deals with application of the LEAN principles to business processes of a typical IT company. The paper discusses LEAN principles amplifying advantages and shortcomings of their application. The authors suggest use of the LEAN principles as a tool to identify improvement potential for IT company's business processes and work-flow efficiency. During a case study the implementation of LEAN principles has been exemplified in business processes of a particular Latvian IT company. The obtained results and conclusions can be used for meaningful and successful application of LEAN principles and methods in projects of other IT companies.
The Need for Structure in Quantum Speedups
2009
Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 7th root of the classical randomized query complexity. (An earlier version of this paper gave the 9th root.) This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al. (2006), we conjecture t…
Span-program-based quantum algorithm for the rank problem
2011
Recently, span programs have been shown to be equivalent to quantum query algorithms. It is an open problem whether this equivalence can be utilized in order to come up with new quantum algorithms. We address this problem by providing span programs for some linear algebra problems. We develop a notion of a high level span program, that abstracts from loading input vectors into a span program. Then we give a high level span program for the rank problem. The last section of the paper deals with reducing a high level span program to an ordinary span program that can be solved using known quantum query algorithms.