13 citations · 37 across the 16 of their papers we have counts for
5 papers · 1 filter
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein
Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially size…
Finding the Minimum-Weight k-Path
Avinatan Hassidim, Orgad Keller, Moshe Lewenstein +1
Given a weighted -vertex graph with integer edge-weights taken from a range , we show that the minimum-weight simple path visiting vertices can be found in time…
Succinct data structures for representing equivalence classes
Moshe Lewenstein, J. Ian Munro, Venkatesh Raman
Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are i…
Orthogonal Range Searching for Text Indexing
Moshe Lewenstein
Text indexing, the problem in which one desires to preprocess a (usually large) text for future (shorter) queries, has been researched ever since the suffix tree was invented in th…
Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing
Amihood Amir, Gianni Franceschini, Roberto Grossi +3
This paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data…