This paper is concerned with practical implementations of approximate string dictionaries that allow edit errors. In this problem, we have as input a dictionary @math of @math strings of total length @math over an alphabet of size @math . Given a bound @math and a pattern @math of length @math , a query has to return all the strings of the dictionary which are at edit distance at most @math from @math , where the edit distance between two strings @math and @math is defined as the minimum-cost sequence of edit operations that transform @math into @math . The cost of a sequence of operations is defined as the sum of the costs of the operations involved in the sequence. In this paper, we assume that each of these operations has unit cost and consider only three operations: deletion of one character, insertion of one character and substitution of a character by another. We present a practical implementation of the data structure we recently proposed and which works only for one error. We extend the scheme to @math . Our implementation has many desirable properties: it has a very fast and space-efficient building algorithm. The dictionary data structure is compact and has fast and robust query time. Finally our data structure is simple to implement as it only uses basic techniques from the literature, mainly hashing (linear probing and hash signatures) and succinct data structures (bitvectors supporting rank queries).
For more than one error, the work of @cite_1 , was the first to present good worst-case performance for any @math . However the bounds are not competitive with the recent works both in terms of space and time for the case of @math . Also the data structure presented there seems rather complicated and incurs a polylogarithmic additive term in the query time which could in practice dominate the total query time. We are not aware of any implementation of that data structure.
@cite_1
2085218027
In this paper, we study the communication complexity for the problem of computing a conjunctive query on a large database in a parallel setting with @math servers. In contrast to previous work, where upper and lower bounds on the communication were specified for particular structures of data (either data without skew, or data with specific types of skew), in this work we focus on worst-case analysis of the communication cost. The goal is to find worst-case optimal parallel algorithms, similar to the work of [18] for sequential algorithms. We first show that for a single round we can obtain an optimal worst-case algorithm. The optimal load for a conjunctive query @math when all relations have size equal to @math is @math , where @math is a new query-related quantity called the edge quasi-packing number, which is different from both the edge packing number and edge cover number of the query hypergraph. For multiple rounds, we present algorithms that are optimal for several classes of queries. Finally, we show a surprising connection to the external memory model, which allows us to translate parallel algorithms to external memory algorithms. This technique allows us to recover (within a polylogarithmic factor) several recent results on the I O complexity for computing join queries, and also obtain optimal algorithms for other classes of queries. We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions deletions) in @math amortized time and connectivity queries in @math worst-case time, where @math is the number of vertices of the graph. This improves the deterministic data structures of Holm, de Lichtenberg, and Thorup (STOC 1998, J.ACM 2001) and Thorup (STOC 2000) which both have @math amortized update time and @math worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard @math instructions. In the approximate dictionary search problem we have to construct a data structure on a set of strings so that we can answer to queries of the kind: find all strings of the set that are similar (according to some string distance) to a given string. In this paper we propose the first data structure for approximate dictionary search that occupies optimal space (up to a constant factor) and able to answer an approximate query for edit distance "1" (report all strings of dictionary that are at edit distance at most "1" from query string) in time linear in the length of query string. Based on our new dictionary we propose a full-text index for approximate queries with edit distance "1" (report all positions of all sub-strings of the text that are at edit distance at most "1" from query string) answering to a query in time linear in the length of query string using space @math in the worst case on a text of length n . Our index is the first index that answers queries in time linear in the length of query string while using space O (n ·poly (log (n ))) in the worst case and for any alphabet size. A longest repeat query on a string, motivated by its applications in many subfields including computational biology, asks for the longest repetitive substring(s) covering a particular string position (point query). In this paper, we extend the longest repeat query from point query to , allowing the search for longest repeat(s) covering any position interval, and thus significantly improve the usability of the solution. Our method for interval query takes a different approach using the insight from a recent work on [1], as the prior work's approach for point query becomes infeasible in the setting of interval query. Using the critical insight from [1], we propose an indexing structure, which can be constructed in the optimal @math time and space for a string of size @math , such that any future interval query can be answered in @math time. Further, our solution can find longest repeats covering any given interval using optimal @math time, where @math is the number of longest repeats covering that given interval, whereas the prior @math -time and space work can find only one candidate for each point query. Experiments with real-world biological data show that our proposal is competitive with prior works, both time and space wise, while providing with the new functionality of interval queries as opposed to point queries provided by prior works. A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, “Is W a substring of A?” to be answered in time @math , where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in @math time in the worst case, versus @math time for suffix arrays. However, an augmented algorithm is given that, regardless of the alphabet size, constructs suffix arrays in @math expected time, albeit with lesser space efficiency. It is ... We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation @math , we show how to construct in @math time a data structure of size @math that answers distance queries in @math time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever @math . * We provide a linear-space exact distance oracle for planar graphs with query time @math for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space @math such that for any pair of nodes at distance D the query time is @math . Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with @math nodes, we can preprocess G in @math time to produce a data structure of size @math that can answer the following queries in @math time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA'05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For @math and space @math , we essentially improve the query time from @math to @math . We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time @math and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (STOC 1983) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM 1997), which had update time @math . All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees. Let @math be a tree space (or tree network) represented by a weighted tree with @math vertices, and @math be a set of @math stochastic points in @math , each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we study the computation of the @math -threshold probability and the expectation of the closest-pair distance of a realization of @math . We propose the first algorithm to compute the @math -threshold probability in @math time for any given threshold @math , which immediately results in an @math -time algorithm for computing the expected closest-pair distance. Based on this, we further show that one can compute a @math -approximation for the expected closest-pair distance in @math time, by arguing that the expected closest-pair distance can be approximated via @math threshold probability queries. For the latter, we study the @math most-likely nearest-neighbor search ( @math -LNN) via a notion called @math most-likely Voronoi Diagram ( @math -LVD). We show that the size of the @math -LVD @math of @math on @math is bounded by @math if the existence probabilities of the points in @math are constant-far from 0. Furthermore, we establish an @math average-case upper bound for the size of @math , by regarding the existence probabilities as i.i.d. random variables drawn from some fixed distribution. Our results imply the existence of an LVD data structure which answers @math -LNN queries in @math time using average-case @math space, and worst-case @math space if the existence probabilities are constant-far from 0. Finally, we also give an @math -time algorithm to construct the LVD data structure. The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes which is undergoing a sequence of edge insertions and deletions, answer queries of the form q(a, b): "Is there a path between nodes a and b?" While data structures for this problem with polylogarithmic amortized time per operation have been known since the mid-1990's, these data structures have Θ(n) worst case time. In fact, no previously known solution has worst case time per operation which is o(√n). We present a solution with worst case times O(log4 n) per edge insertion, O(log5 n) per edge deletion, and O(log n log log n) per query. The answer to each query is correct if the answer is "yes" and is correct with high probability if the answer is "no". The data structure is based on a simple novel idea which can be used to quickly identify an edge in a cutset. Our technique can be used to simplify and significantly speed up the preprocessing time for the emergency planning problem while matching previous bounds for an update, and to approximate the sizes of cutsets of dynamic graphs in time O(min |S|, |V | ) for an oblivious adversary. We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(logBN + K B) block transfers in the worst case, where K is the size of the query output. The problems we study are three-sided range reporting, 3-d dominance reporting, and 3-d halfspace range reporting. We prove that, in order to achieve the above query bound or even a bound of O((logB N)c (1 + K B)), for any constant c > 0, the structure has to use Ohmega(N (log log N)e) space, where e > 0 is a constant that depends on c and on the constant hidden in the big-Oh notation of the query bound. Our result has a number of interesting consequences. The first one is a new type of separation between the I O model and the cache-oblivious model, as I O-efficient data structures with the optimal query bound and using linear or O(N logAST N) space are known for the above problems. The second consequence is the non-existence of a linear-space cache-oblivious persistent B-tree with worst-case optimal 1-d range reporting queries. Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a novel algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a full conjunctive query in terms of the sizes of the individual relations in the body of the query. These bounds, however, are not constructive: they rely on Shearer's entropy inequality which is information-theoretic. Thus, the previous results leave open the question of whether there exist algorithms whose running time achieve these optimal bounds. An answer to this question may be interesting to database practice, as we show in this paper that any project-join plan is polynomially slower than the optimal bound for some queries. We construct an algorithm whose running time is worst-case optimal for all natural join queries. Our result may be of independent interest, as our algorithm also yields a constructive proof of the general fractional cover bound by Atserias, Grohe, and Marx without using Shearer's inequality. In addition, we show that this bound is equivalent to a geometric inequality by Bollobas and Thomason, one of whose special cases is the famous Loomis-Whitney inequality. Hence, our results algorithmically prove these inequalities as well. Finally, we discuss how our algorithm can be used to compute a relaxed notion of joins. Given a static array of @math totally ordered objects, the range minimum query problem is to build a data structure that allows us to answer efficiently subsequent on-line queries of the form “what is the position of a minimum element in the subarray ranging from @math to @math ?”. We focus on two settings, where (1) the input array is available at query time, and (2) the input array is available only at construction time. In setting (1), we show new data structures (a) of size @math bits and query time @math for any positive integer function @math for an arbitrary constant @math , or (b) with @math bits and @math query time, where @math denotes the empirical entropy of @math th order of the input array. In setting (2), we give a data structure of size @math bits and query time @math . All data structures can be constructed in linear time and almost in-place. We present a randomized algorithm for dynamic graph connectivity. With failure probability less than @math (for any constant @math we choose), our solution has worst case running time @math per edge insertion, @math per edge deletion, and @math per query, where @math is the number of vertices. The previous best algorithm has worst case running time @math per edge insertion and @math per edge deletion. The improvement is made by reducing the randomness used in the previous result, so that we save a @math factor in update time. Specifically, kapron2013dynamic uses @math copies of a data structure in order to boost a success probability from @math to @math . We show that, in fact though, because of the special structure of their algorithm, this boosting via repetition is unnecessary. Rather, we can still obtain the same correctness guarantee with high probability by arguing via a new invariant, without repetition. The k-means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii (FOCS 2006) aimed at closing this gap, and they proved a bound of @math on the smoothed running-time of the k-means method, where n is the number of data points and @math is the standard deviation of the Gaussian perturbation. This bound, though better than the worst-case bound, is still much larger than the running-time observed in practice. We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in @math and @math . Second, we prove an upper bound of @math , where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for @math . Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances. [See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the @math -Approximate Near Neighbor Search problem. For the @math -dimensional Euclidean space and @math -point datasets, we develop a data structure with space @math and query time @math for every @math such that: This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor @math , improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for @math , improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes. We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph @math with @math vertices, and define (for @math ) @math . Our aim is to estimate @math within a multiplicative error of @math (for a given approximation parameter @math ) in sublinear time. We consider the sparse graph model that allows access to: uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of @math (the average degree), @math queries suffice for any constant @math (Feige, SICOMP 06 and Goldreich-Ron, RSA 08). Gonen-Ron-Shavitt (SIDMA 11) extended this result to all integral @math , by designing an algorithms that performs @math queries. We design a new, significantly simpler algorithm for this problem. In the worst-case, it exactly matches the bounds of Gonen-Ron-Shavitt, and has a much simpler proof. More importantly, the running time of this algorithm is connected to the degeneracy of @math . This is (essentially) the maximum density of an induced subgraph. For the family of graphs with degeneracy at most @math , it has a query complexity of @math . Thus, for the class of bounded degeneracy graphs (which includes all minor closed families and preferential attachment graphs), we can estimate the average degree in @math queries, and can estimate the variance of the degree distribution in @math queries. This is a major improvement over the previous worst-case bounds. Our key insight is in designing an estimator for @math that has low variance when @math does not have large dense subgraphs. We study the aggregate group nearest neighbor searching for the MAX operator in the plane. For a set @math of @math points and a query set @math of @math points, the query asks for a point of @math whose maximum distance to the points in @math is minimized. We present data structures for answering such queries for both @math and @math distance measures. Previously, only heuristic and approximation algorithms were given for both versions. For the @math version, we build a data structure of O(n) size in @math time, such that each query can be answered in @math time. For the @math version, we build a data structure in @math time and @math space, such that each query can be answered in @math time, and alternatively, we build a data structure in @math time and space for any @math , such that each query can be answered in @math time. Further, we extend our result for the @math version to the top- @math queries where each query asks for the @math points of @math whose maximum distances to @math are the smallest for any @math with @math : We build a data structure of O(n) size in @math time, such that each top- @math query can be answered in @math time. Given two locations s and t in a road network, a distance query returns the minimum network distance from s to t, while a shortest path query computes the actual route that achieves the minimum distance. These two types of queries find important applications in practice, and a plethora of solutions have been proposed in past few decades. The existing solutions, however, are optimized for either practical or asymptotic performance, but not both. In particular, the techniques with enhanced practical efficiency are mostly heuristic-based, and they offer unattractive worst-case guarantees in terms of space and time. On the other hand, the methods that are worst-case efficient often entail prohibitive preprocessing or space overheads, which render them inapplicable for the large road networks (with millions of nodes) commonly used in modern map applications. This paper presents Arterial Hierarchy (AH), an index structure that narrows the gap between theory and practice in answering shortest path and distance queries on road networks. On the theoretical side, we show that, under a realistic assumption, AH answers any distance query in O(log α) time, where α = dmax dmin, and dmax (resp. dmin) is the largest (resp. smallest) L∞ distance between any two nodes in the road network. In addition, any shortest path query can be answered in O(k + log α) time, where k is the number of nodes on the shortest path. On the practical side, we experimentally evaluate AH on a large set of real road networks with up to twenty million nodes, and we demonstrate that (i) AH outperforms the state of the art in terms of query time, and (ii) its space and pre-computation overheads are moderate. (MATH) Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph @math and a subset of vertices @math , to support insertions and deletions in @math and connectivity queries (are two vertices connected @?) in the subgraph induced by @math . We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using an elegant combination of several simple ideas. Our method requires linear space, @math amortized update time, and @math query time, where @math is the matrix multiplication exponent and @math hides polylogarithmic factors. Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks to preprocess a string of length @math such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold @math . Subsequent authors have reduced their time and space bounds such that, when @math is given at preprocessing time, we need either @math space and optimal @math query time or linear space and @math query time, where @math is the alphabet size. In this paper we give the first linear-space solution with optimal @math query time. For the case when @math is given at query time, we significantly improve previous bounds, achieving either @math space and optimal @math query time or compressed space and @math query time. Along the way, we consider the complementary problem of parameterized range minority that was recently introduced by (2012), who achieved linear space and @math query time even for variable @math . We improve their solution to use either nearly optimally compressed space with no slowdown, or optimally compressed space with nearly no slowdown. Some of our intermediate results, such as density-sensitive query time for one-dimensional range counting, may be of independent interest.