Counting inversions in lists

Anupam Gupta; Francis X. Zane

Counting inversions in lists

Anupam Gupta, Francis X. Zane

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

In a recent paper, Ajtai et al. [1] give a streaming algorithm to count the number of inversions in a stream L ∈ [m]ⁿ using two passes and O(ε^-1 √n log n(log m + log n)) space. Here, we present a simple randomized streaming algorithm for the same problem that uses one pass and O(ε^-3 log² n log m) space. Our algorithm is based on estimating quantiles of the items already seen in the stream, and using that to estimate the number of inversions involving each element.

Original language	English (US)
Pages	253-254
Number of pages	2
State	Published - 2003
Event	Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998

Other

Other	Configuralble Computing: Technology and Applications
Country/Territory	United States
City	Boston, MA
Period	11/2/98 → 11/3/98

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{be3b569394e94d0fb8da83e149bb1bc3,

title = "Counting inversions in lists",

abstract = "In a recent paper, Ajtai et al. [1] give a streaming algorithm to count the number of inversions in a stream L ∈ [m]n using two passes and O(ε-1 √n log n(log m + log n)) space. Here, we present a simple randomized streaming algorithm for the same problem that uses one pass and O(ε-3 log2 n log m) space. Our algorithm is based on estimating quantiles of the items already seen in the stream, and using that to estimate the number of inversions involving each element.",

author = "Anupam Gupta and Zane, {Francis X.}",

year = "2003",

language = "English (US)",

pages = "253--254",

note = "Configuralble Computing: Technology and Applications ; Conference date: 02-11-1998 Through 03-11-1998",

}

TY - CONF

T1 - Counting inversions in lists

AU - Gupta, Anupam

AU - Zane, Francis X.

PY - 2003

Y1 - 2003

N2 - In a recent paper, Ajtai et al. [1] give a streaming algorithm to count the number of inversions in a stream L ∈ [m]n using two passes and O(ε-1 √n log n(log m + log n)) space. Here, we present a simple randomized streaming algorithm for the same problem that uses one pass and O(ε-3 log2 n log m) space. Our algorithm is based on estimating quantiles of the items already seen in the stream, and using that to estimate the number of inversions involving each element.

AB - In a recent paper, Ajtai et al. [1] give a streaming algorithm to count the number of inversions in a stream L ∈ [m]n using two passes and O(ε-1 √n log n(log m + log n)) space. Here, we present a simple randomized streaming algorithm for the same problem that uses one pass and O(ε-3 log2 n log m) space. Our algorithm is based on estimating quantiles of the items already seen in the stream, and using that to estimate the number of inversions involving each element.

UR - http://www.scopus.com/inward/record.url?scp=0038416086&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038416086&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0038416086

SP - 253

EP - 254

T2 - Configuralble Computing: Technology and Applications

Y2 - 2 November 1998 through 3 November 1998

ER -

Counting inversions in lists

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this