S. Muthukrishnan
- AL+95.R. Agarwal, K. Lin, H. Sawhney and K. Shim. Fast similarity search in the presence of noise, scaling and translation in time-series databases. Proc. 21 st VLDB conf, 1995. Google Scholar
Digital Library
- CL90.W. Chang and E. Lawler, Approximate String Matching in Sublinear Expected Time, Proceedings of IEEE Symposium on Foundations of Computer Science, (1990).Google ScholarDigital Library
- CP+00.G. Cormode, M. Paterson, S. C. Sahinalp and U. Vishkin. Communication Complexity of Document Exchange. Proc. ACM-SIAM Symp. on Discrete Algorithms, 2000. Google ScholarDigital Library
- CV86.R. Cole and U. Vishkin, Deterministic Coin Tossing and Accelerating Cascades, Micro and Macro Techniques for Designing Parallel Algorithms, Proceedings of ACM Symposium on Theory of Computing, (1986). Google ScholarDigital Library
- FI99.M. Farach-Colton and P. Indyk. Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. Proc. IEEE Syrup. Foundations of Computer Science, 1999. Google ScholarDigital Library
- G.GeIAssemble. http: . .staffa.wi .mit.edu / gcg / gelas sembl e. html.Google Scholar
- GD91.M. Oribskov and J. Devereux Sequence Analysis Primer, Stockton Press, 1991.Google Scholar
- I98.P. Indyk. On Approximate Nearest Neighbors in Non-Euclidean Spaces. Proc IEEE Symp on Foundations of Computer Science, 1998, 148- 155. Google ScholarDigital Library
- IM98.P. indyk and R. Motwani. Approximate Nearest Neighbors: Towards Remving the Curse of Dimensionality. Proc. ACM Symp. on Theory of Computing, 1998, 604-613. Google ScholarDigital Library
- J97.J. Kleinberg. Two Algorithms for Nearest Neighbor Search in High Dimensions. Proc. A CM Symp. on Theory of Computing, 1997, 599-608. Google ScholarDigital Library
- KMR72.R. Karp, R. Miller and A. Rosenberg, Rapid Identification of Repeated Patterns in Strings, Trees, and Arrays, Proceedings of ACM Symposium on Theory of Computing, (1972). Google ScholarDigital Library
- KOR98.E. Kushilevitz, R. Ostrovsky and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. Proc. ACM Symposium on Theory of Computing, 1998, 614-623. Google ScholarDigital Library
- LT96.D. Lopresti and A. Tomkins. Block edit models for approximate string matching. Theoretical Computer Science, 1996. Google ScholarDigital Library
- SK83.D. Sankoff and J. Kruskal, Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison- Wesley, Reading, Mass., 1983.Google Scholar
- LV89.G. Landau and U. Vishkin, Fast Parallel and Serial Approximate String Matching, Journal of Algorithms, 10, (1989):158-169. Google ScholarDigital Library
- Lev66.V.I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals, Cybernetics and Control Theory, 10(8):707-710, 1966.Google Scholar
- SV96.S. C. Sahinalp and U. Vishkin, Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm, Proceedings of IEEE Symposium on Foundations of Computer Science, (1996). Google ScholarDigital Library
- Se80.P. Sellers, The Theory and Computation of Evolutionary Distances: Pattern Recognition. Journal of Algorithms, 1, (1980):359-373.Google ScholarCross Ref
- T84.W.F. Tichy, The string-to-string correction problem with block moves. ACM Trans. on Computer Systems, 2(4): 309-321, 1984. Google ScholarDigital Library
- Uk83.E. Ukkonen, On Approximate String Matching. Proceedings of Conference on Foundations of Computation Theory, (1983). Google ScholarDigital Library
Index Terms
- Approximate nearest neighbors and sequence comparison with block operations
Recommendations
On Approximate Nearest Neighbors under l∞ Norm
The nearest neighbor search (NNS) problem is the following: Given a set of n points P={p1, , pn} in some metric space X, preprocess P so as to efficiently answer queries which require finding a point in P closest to a query point q X. The approximate ...
Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours
Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern RecognitionMany pattern recognition tasks make use of the k nearest neighbour (k-NN) technique. In this paper we are interested on fast k- NN search algorithms that can work in any metric space i.e. they are not restricted to Euclidean-like distance functions. ...
Simple and Practical Sequence Nearest Neighbors with Block Operations
CPM '02: Proceedings of the 13th Annual Symposium on Combinatorial Pattern MatchingSequence nearest neighbors problemc an be defined as follows. Given a database D of n sequences, preprocess D so that given any query sequence Q , one can quickly find a sequence S in D for which d(S,Q) d(S, T) for any other sequence T ...
Comments