18 citations · 79 across the 27 of their papers we have counts for
5 papers · 1 filter
Faster Clustering via Preprocessing
Tsvi Kopelowitz, Robert Krauthgamer
We examine the efficiency of clustering a set of points, when the encompassing metric space may be preprocessed in advance. In computational problems of this genre, there is a firs…
On-line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List
Tsvi Kopelowitz
The problem of Text Indexing is a fundamental algorithmic problem in which one wishes to preprocess a text in order to quickly locate pattern queries within the text. In the ever e…
Sparse Suffix Tree Construction with Small Space
Philip Bille, Inge Li Gørtz, Tsvi Kopelowitz +2
We consider the problem of constructing a sparse suffix tree (or suffix array) for suffixes of a given text of size , using only words of space during constructio…
Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting
Tsvi Kopelowitz, Nimrod Talmon
The selection problem, where one wishes to locate the smallest element in an unsorted array of size , is one of the basic problems studied in computer science. The main…
Cross-Document Pattern Matching
Gregory Kucherov, Yakov Nekrich, Tatiana Starikovskaya
We study a new variant of the string matching problem called cross-document string matching, which is the problem of indexing a collection of documents to support an efficient sear…