New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems
作者： Moses Charikar , Piotr Indyk , Rina Panigrahy
关键词: Range searching 、 Partial match 、 General problem 、 Algorithm 、 Binary logarithm 、 Data structure 、 Combinatorics 、 k-nearest neighbors algorithm 、 Range query (data structures) 、 Mathematics
摘要: We consider the subset query problem, defined as follows: given a set P of N subsets universe U, |U| = m, build data structure, which for any Q ? U detects if there is such that P. This essentially equivalent to partial match problem and fundamental in many areas. In this paper we present first (to our knowledge) algorithms, achieve non-trivial space time bounds m ?(log N). particular, two algorithms with following tradeoffs: - 2O (mlog2 ?c/ log N) space, O(N/2c) time, c Nmc O(mN/c) extend these results more general orthogonal range searching (both exact approximate versions), intersection versions nearest neighbor l?.
springer.com
core.ac.uk
sci-hub.st 参考文章(16)
Ronald Linn Rivest, Analysis of associative retrieval algorithms. Stanford University. ,(1974)
Piotr Indyk, Rajeev Motwani, High-dimensional computational geometry ,(2000)
P. Indyk, On approximate nearest neighbors in non-Euclidean spaces foundations of computer science. pp. 148- 155 ,(1998) , 10.1109/SFCS.1998.743438
David Eppstein, S. Muthukrishnan, Internet packet filter management and rectangle geometry symposium on discrete algorithms. pp. 827- 835 ,(2001) , 10.5555/365411.365791
V. Srinivasan, S. Suri, G. Varghese, Packet classification using tuple space search acm special interest group on data communication. ,vol. 29, pp. 135- 146 ,(1999) , 10.1145/316188.316216
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces symposium on the theory of computing. pp. 614- 623 ,(1998) , 10.1145/276698.276877
Allan Borodin, Rafail Ostrovsky, Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems Proceedings of the thirty-first annual ACM symposium on Theory of computing - STOC '99. pp. 312- 321 ,(1999) , 10.1145/301250.301330
A. Feldman, S. Muthukrishnan, Tradeoffs for packet classification international conference on computer communications. ,vol. 3, pp. 1193- 1202 ,(2000) , 10.1109/INFCOM.2000.832493
Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors Communications of the ACM. ,vol. 13, pp. 422- 426 ,(1970) , 10.1145/362686.362692
George S. Lueker, A data structure for orthogonal range queries 19th Annual Symposium on Foundations of Computer Science (sfcs 1978). pp. 28- 34 ,(1978) , 10.1109/SFCS.1978.1