Dong Deng

Dong Deng

Auto-generated profile, based on publicly available information

Dong Deng

Rutgers University, New Brunswick, NJ, USA

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
12 March 2024 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
CZChaoji Zuo
Chaoji Zuo
MQMiao Qiao
Miao Qiao
WZWenchao Zhou
Wenchao Zhou
FLFeifei Li
Feifei Li
DDDong Deng
Dong Deng
Effective vector representation models, e.g., word2vec and node2vec, embed real-world objects such as images and documents in high dimensional vector space. In the meanwhile, the objects are often associated with attributes such as timestamps and prices. Many scenarios need to jointly query the vector representations of the objects together with their attributes. These queries can be formalized as range-filtering approximate nearest neighbor search (ANNS) queries. Specifically, given a collection of data vectors, each associated with an attribute value whose domain has a total order. The range-filtering ANNS consists of a query range and a query vector. It finds the approximate nearest neighbors of the query vector among all the data vectors whose attribute values fall in the query range. Existing approaches suffer from a rapidly degrading query performance when the query range width shifts. The query performance can be optimized by a solution that builds an ANNS index for every possible query range; however, the index time and index size become prohibitive -- the number of query ranges is quadratic to the number n of data vectors. To overcome these challenges, for the query range contains all attribute values smaller than a user-provided threshold, we design a structure called the segment graph whose index time and size are the same as a single ANNS index, yet can losslessly compress the n ANNS indexes, reducing the indexing cost by a factor of Ω(n). To handle general range queries, we propose a 2D segment graph with average-case index size O(n log n) to compress n segment graphs, breaking the quadratic barrier. Extensive experiments conducted on real-world datasets show that our proposed structures outperformed existing methods significantly; our index also exhibits superior scalability.

13 June 2023 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
ZPZhencan Peng
Zhencan Peng
ZWZhizhi Wang
Zhizhi Wang
DDDong Deng
Dong Deng
Recent studies show that large language models (LLM) unintendedly memorize part of the training data, which brings serious privacy risks. For example, it has been shown that over 1% of tokens generated unprompted by an LLM are part of sequences in the training data. However, current studies mainly focus on the exact memorization behaviors. In this paper, we propose to evaluate how many generated texts have near-duplicates (e.g., only differ by a couple of tokens out of 100) in the training corpus. A major challenge of conducting this evaluation is the huge computation cost incurred by near-duplicate sequence searches. This is because modern LLMs are trained on larger and larger corpora with up to 1 trillion tokens. What's worse is that the number of sequences in a text is quadratic to the text length. To address this issue, we develop an efficient and scalable near-duplicate sequence search algorithm in this paper. It can find (almost) all the near-duplicate sequences of the query sequence in a large corpus with guarantees. Specifically, the algorithm generates and groups the min-hash values of all the sequences with at least t tokens (as very short near-duplicates are often irrelevant noise) in the corpus in linear time to the corpus size. We formally prove that only 2 n+1/t+1 -1 min-hash values are generated for a text with n tokens in expectation. Thus the index time and size are reasonable. When a query arrives, we find all the sequences sharing enough min-hash values with the query using inverted indexes and prefix filtering. Extensive experiments on a few large real-world LLM training corpora show that our near-duplicate sequence search algorithm is efficient and scalable.

27 September 2018
Verified
Conference Paper
Open access
PDF file
DDDong Deng
Dong Deng
LJLiping Jing
Liping Jing
JYJian Yu
Jian Yu
SSShaolong Sun
Shaolong Sun
Haofei ZhouHaofei Zhou
Haofei Zhou

2 April 2024 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Closed access
JLJiesong Liu
Jiesong Liu
FZFeng Zhang
Feng Zhang
LLLv Lu
Lv Lu
CQChang Qi
Chang Qi
XGXiaoguang Guo
Xiaoguang Guo
XDXiaoyong Du
Xiaoyong Du
AI and GPU technologies have been widely applied to solve Big Data problems. The total data volume worldwide reaches 200 zettabytes in 2022. How to efficiently index the required content among massive data becomes serious. Recently, a promising learned index has been proposed to address this challenge: It has extremely high efficiency while retaining marginal space overhead. However, we notice that previous learned indexes have mainly focused on CPU architecture, while ignoring the advantages of GPU. Because traditional indexes like B-Tree, LSM, and bitmap have greatly benefited from GPU acceleration, a combination of a learned index and GPU has great potentials to reach tremendous speedups. In this paper, we propose a GPU-based learned index, called G-Learned Index, to significantly improve the performance of learned index structures. The primary challenges in developing G-Learned Index lie in the use of thousands of GPU cores including minimization of synchronization and branch divergence, data structure design for parallel operations, and usage of memory bandwidth including limited memory transactions and multi-memory hierarchy. To overcome these challenges, a series of novel technologies are developed, including efficient thread organization, succinct data structures, and heterogeneous memory hierarchy utilization. Compared to the state-of-the-art learned index, the proposed G-Learned Index achieves an average of 174× speedup (and 107× of its parallel version). Meanwhile, we attain 2× less query time over the state-of-the-art GPU B-Tree. Our further exploration of range queries shows that G-Learned Index is $17\times$ faster than CPU multi-dimensional learned index.

27 June 2024 in The VLDB Journal
Verified
Journal Article
Closed access
PDF file
YXYifei Xia
Yifei Xia
FZFeng Zhang
Feng Zhang
QXQingyu Xu
Qingyu Xu
MZMingde Zhang
Mingde Zhang
ZYZhiming Yao
Zhiming Yao
SMSiqi Ma
Siqi Ma

30 September 2024 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
ZPZhencan Peng
Zhencan Peng
YZYuheng Zhang
Yuheng Zhang
DDDong Deng
Dong Deng
This paper studies the near-duplicate text alignment problem under the constraint of Jaccard similarity. Specifically, given a collection of long texts and a short query text, this problem finds all the subsequences in each text whose Jaccard similarities to the query are no smaller than a given threshold. Near-duplicate text alignment is computationally intensive. This is because there are O(n 2 ) subsequences in a text with n tokens. To remedy this issue, a few recent studies propose to first generate the min-hash sketch of every subsequence in each text and then find all the subsequences whose min-hash sketches are similar to that of the query. They introduce the concept of "compact windows" and show that the O(n 2 k) min-hashes in a text with n tokens can be losslessly compressed in compact windows using O(nk) space, where k is the sketch size. However, the space cost O(nk) is still too high for long texts, especially when the sketch size k is large. To address this issue, we propose to use One Permutation Hashing (OPH) to generate the min-hash sketch and introduce the concept of "OPH compact windows". Although the size of each sketch remains the same, which is O(k), we prove that all the O(n 2 k) min-hashes generated by OPH in a text with n tokens can be losslessly compressed in OPH compact windows using only O(n+k) space. Note the generation of OPH compact windows does not necessitate the enumeration of the O(n 2 k) min-hashes. Moreover, we develop an algorithm to find all the sketches in a text similar to that of the query directly from OPH compact windows, along with three optimizations.We conduct extensive experiments on three real-world datasets. Empirical results show our proposed algorithms significantly outperformed existing methods in terms of index cost and query latency and scaled well.