357 citations · 1.3k across the 33 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2010★ 9 cited
Random Projection Trees Revisited
Aman Dhesi, Purushottam Kar
The Random Projection Tree structures proposed in [Freund-Dasgupta STOC08] are space partitioning data structures that automatically adapt to various notions of intrinsic dimension…
cs.DS2010
Estimating small frequency moments of data stream: a characteristic function approach
Sumit Ganguly, Purushottam Kar
A data stream is viewed as a sequence of updates of the form to an -dimensional integer frequency vector , where the update changes to $f_i + v…
cs.DS2010
On Estimating the First Frequency Moment of Data Streams
Sumit Ganguly, Purushottam Kar
Estimating the first moment of a data stream defined as $F_1 = \sum_{i \in \{1, 2, \ldots, n\}} \abs{f_i}$ to within -relative error with high probability is a basic and i…