Efficient block-based sampling algorithm for aggregation query processing on duplicate charged records

doi:10.11772/j.issn.1001-9081.2017112632

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (6): 1596-1600.DOI: 10.11772/j.issn.1001-9081.2017112632

Previous Articles Next Articles

Efficient block-based sampling algorithm for aggregation query processing on duplicate charged records

PAN Mingyu¹, ZHANG Lu¹, LONG Guobiao¹, LI Xianglong¹, MA Dongxue¹, XU Liang²

1. State Grid Beijing Electric Power Company, Beijing 100075, China;
2. NARI Group, Beijing 102299, China

Received:2017-11-06 Revised:2018-02-05 Online:2018-06-10 Published:2018-06-13
Supported by:
This work is partially supported by the Science and Technology Project of State Grid Corporation (52020116000j).

用于重复充电运营记录的基于块采样的高效聚集查询算法

潘鸣宇¹, 张禄¹, 龙国标¹, 李香龙¹, 马冬雪¹, 徐亮²

1. 国网北京市电力公司, 北京 100075;
2. 南瑞集团, 北京 102299

通讯作者: 潘鸣宇
作者简介:潘鸣宇(1985-),男,北京人,高级工程师,硕士,主要研究方向:充换电运营数据分析;张禄(1984-),男,北京人,高级工程师,博士,主要研究方向:充换电运营数据分析;龙国标(1967-),男,北京人,高级工程师,主要研究方向:充换电运营数据分析;李香龙(1980-),男,河北石家庄人,高级工程师,硕士,主要研究方向:充换电运营数据分析;马冬雪(1989-),女,北京人,中级经济师,硕士,主要研究方向:充换电运营咨询;徐亮(1981-),男,辽宁沈阳人,高级工程师,硕士,主要研究方向:充换电运营数据分析。
基金资助:
国家电网公司总部科技项目（52020116000j）。

Abstract

Abstract: The existing query analysis methods usually treat the entity resolution as an offline preprocessing process to clean the whole data set. However, with the continuous increasing of data size, such offline cleaning mode with high computing complexity has been difficult to meet the needs of real-time analysis in most applications. In order to solve the problem of aggregation query on duplicate charged records, a new method integrating entity resolution with approximate aggregation query processing was proposed. Firstly, a block-based sampling strategy was adopted to collect samples. Then, an entity recognition method was used to identify the duplicate entities on the sampled samples. Finally, the unbiased estimation of aggregated results was reconstructed according to the results of entity recognition. The proposed method avoids the time cost of identifying all entities, and returns the query results that satisfy user needs by identifying only a small number of sample data. The experimental results on both real dataset and synthetic dataset demonstrate the efficiency and reliability of the proposed method.

Key words: big data, entity resolution, aggregation query, block sampling, distributed computing

摘要： 现有查询分析方法通常将实体识别作为线下预处理过程清洗整个数据集，然而，随着数据规模的不断增大，这种高计算复杂性的线下清洗模式已经很难满足实时性分析应用的需求。针对重复充电运营记录上的聚集查询问题，提出一种将近似聚集查询处理与实体识别相结合的方法。首先，通过基于块的采样策略采集样本；然后，在采集到的样本上利用实体识别方法识别出重复的实体；最后，根据实体识别的结果重构得到聚集结果的无偏估计。所提方法避免了识别全部实体的时间代价，通过识别少量样本数据即可返回满足用户需求的查询结果。真实数据集和合成数据集上的实验结果验证了所提方法的高效性和可靠性。

关键词: 大数据, 实体识别, 聚集查询, 块采样, 分布式计算

CLC Number:

TP311

PAN Mingyu, ZHANG Lu, LONG Guobiao, LI Xianglong, MA Dongxue, XU Liang. Efficient block-based sampling algorithm for aggregation query processing on duplicate charged records[J]. Journal of Computer Applications, 2018, 38(6): 1596-1600.

潘鸣宇, 张禄, 龙国标, 李香龙, 马冬雪, 徐亮. 用于重复充电运营记录的基于块采样的高效聚集查询算法[J]. 计算机应用, 2018, 38(6): 1596-1600.

References

[1] ELMAGARMID A K, IPEIROTIS P G, VERYKIOS V S. Duplicate record detection:a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(1):1-16.
[2] KÖPCKE H, RAHM E. Frameworks for entity matching:a comparison[J]. Data & Knowledge Engineering, 2010, 69(2):197-210.
[3] HERNÁNDEZ M A, STOLFO S J. The merge/purge problem for large databases[C]//Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. New York:ACM, 1995:127-138.
[4] 王宏志,樊文飞.复杂数据上的实体识别技术研究[J].计算机学报,2011,34(10):1843-1852.(WANG H Z, FAN W F. Object identification on complex data:a survey[J]. Chinese Journal of Computers, 2011, 34(10):1843-1852.)
[5] 孙琛琛,申德荣,寇月,等.面向关联数据的联合式实体识别方法[J].计算机学报,2015,38(9):1739-1754.(SUN C C, SHEN D R, KOU Y, et al. A related data oriented joint entity resolution approach[J]. Chinese Journal of Computers, 2015, 38(9):1739-1754.)
[6] 寇月,申德荣,刘恒,等.异构网络中关联实体识别模型及增量式验证算法研究[J].计算机学报,2013,36(10):2096-2108.(KOU Y, SHEN D R, LIU H, et al. Research on related entity identification model and incremental verification algorithm for heterogeneous networks[J]. Chinese Journal of Computers, 2013, 36(10):2096-2108.)
[7] ANANTHAKRISHNA R, CHAUDHURI S, GANTI V. Eliminating fuzzy duplicates in data warehouses[C]//Proceedings of the 28th International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann, 2002:586-597.
[8] BHATTACHARYA I, GETOOR L. Collective entity resolution in relational data[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1):Article No. 5.
[9] ALTWAIJRY H, KALASHNIKOV D V, MEHROTRA S. Query-driven approach to entity resolution[J]. Proceedings of the VLDB Endowment, 2013, 6(14):1846-1857.
[10] ALTWAIJRY H, MEHROTRA S, KALASHNIKOV D V. QuERy:a framework for integrating entity resolution with query processing[J]. Proceedings of the VLDB Endowment, 2015, 9(3):120-131.
[11] BHATTACHARYA I, GETOOR L. Query-time entity resolution[J]. Journal of Artificial Intelligence Research, 2007, 30(1):621-657.
[12] IOANNOU E, NEJDL W, NIEDERÉE C, et al. On-the-fly entity-aware query processing in the presence of linkage[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2):429-438.
[13] SISMANIS Y, WANG L, FUXMAN A, et al. Resolution-aware query answering for business intelligence[C]//Proceedings of the 2009 IEEE 25th International Conference on. Washington, DC:IEEE Computer Society, 2009:976-987.
[14] ALTOWIM Y, KALASHNIKOV D V, MEHROTRA S. Progressive approach to relational entity resolution[J]. Proceedings of the VLDB Endowment, 2014, 7(11):999-1010.
[15] WHANG S E, MARMAROS D, GARCIA-MOLINA H. Pay-as-you-go entity resolution[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(5):1111-1124.
[16] GRUENHEID A, DONG X L, SRIVASTAVA D. Incremental record linkage[J]. Proceedings of the VLDB Endowment, 2014, 7(9):697-708.
[17] WHANG S E, GARCIA-MOLINA H. Incremental entity resolution on rules and data[J]. The VLDB Journal, 2014, 23(1):77-102.
[18] CORMODE G, GAROFALAKIS M, HAAS P J, et al. Synopses for massive data:samples, histograms, wavelets, sketches[J]. Foundations and Trends in Databases, 2012, 4(1/2/3):1-294.
[19] GAROFALAKIS N, GIBBONS P B. Approximate query processing:taming the terabytes[C]//VLDB 2001:Proceedings of 27th International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann, 2001:169-212.
[20] ACHARYA S, GIBBONS P B, POOSALA V, et al. The Aqua approximate query answering system[C]//Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. New York:ACM, 1999:574-576.
[21] AGARWAL S, MOZAFARI B, PANDA A, et al. BlinkDB:queries with bounded errors and bounded response times on very large data[C]//Proceedings of the 8th ACM European Conference on Computer Systems. New York:ACM, 2013:29-42.
[22] BABCOCK B, CHAUDHURI S, DAS G. Dynamic sample selection for approximate query processing[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of data. New York:ACM, 2003:539-550.
[23] CHAUDHURI S, DAS G, NARASAYYA V. Optimized stratified sampling for approximate query processing[J]. ACM Transactions on Database Systems, 2007, 32(2):9.
[24] CONDIE T, CONWAY N, ALVARO P, et al. Online aggregation and continuous query support in MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. New York:ACM, 2010:1115-1118.
[25] HELLERSTEIN J M, HASS P J, WANG H J. Online aggregation [C]// Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1997: 171-182.
[26] PANSARE N, BORKAR V R, JERMAINE C, et al. Online aggregation for large MapReduce jobs [J]. Proceedings of the VLDB Endowment, 2011, 4(11): 1135-1145.
[27] WU S, JIANG S X, OOI B C, et al. Distributed online aggregations [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 443-454.
[28] WANG J N, KRISHNAN S, FRANKLIN M J, et al. A sample-and-clean framework for fast and accurate query processing on dirty data [C]// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2014: 469-480.

Efficient block-based sampling algorithm for aggregation query processing on duplicate charged records

用于重复充电运营记录的基于块采样的高效聚集查询算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	WANG Zhoukai, ZHANG Jiong, MA Weigang, WANG Huaijun. Parallel decompression algorithm for high-speed train monitoring data [J]. Journal of Computer Applications, 2021, 41(9): 2586-2593.
[2]	ZHOU Xiang, ZHAI Junhai, HUANG Yajie, SHEN Ruicai, HOU Yingzhen. Instance selection algorithm for big data based on random forest and voting mechanism [J]. Journal of Computer Applications, 2021, 41(1): 74-80.
[3]	CAO Cejun, LIU Ju. Overview of modeling method of emergency organization decision in disaster operations management [J]. Journal of Computer Applications, 2020, 40(7): 2142-2149.
[4]	ZHU Xiaojie, ZHAO Zihao, DU Yi. PiFlow: model driven big data pipeline framework [J]. Journal of Computer Applications, 2020, 40(6): 1638-1647.
[5]	WU Wenli, LIU Guohua, ZHANG Junbao. Complexity analysis of functional query answering on big data [J]. Journal of Computer Applications, 2020, 40(2): 416-419.
[6]	HAN Junying, ZHANG Zhenyu, KONG Deshi. Distributed multi-task allocation method for user area in mobile crowd sensing [J]. Journal of Computer Applications, 2020, 40(2): 358-362.
[7]	LI Ziying, SHI Zhenguo. Scheduling method for big data tasks [J]. Journal of Computer Applications, 2020, 40(10): 2923-2928.
[8]	ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms [J]. Journal of Computer Applications, 2019, 39(7): 1869-1882.
[9]	MA Jiangang, MA Yinglong. Semantic-driven learning and classification method of judicial documents [J]. Journal of Computer Applications, 2019, 39(6): 1696-1700.
[10]	JI Lina, CHEN Kai, YU Yanwei, SONG Peng, WANG Shuying, WANG Chenrui. Vehicle type mining and application analysis based on urban traffic big data [J]. Journal of Computer Applications, 2019, 39(5): 1343-1350.
[11]	ZHANG Yitian, YU Jiong, LU Liang, LI Ziyang. Task scheduling strategy based on data stream classification in Heron [J]. Journal of Computer Applications, 2019, 39(4): 1106-1116.
[12]	WANG Xuefei, DING Weilong. Short-term traffic prediction method on big data in highway domain [J]. Journal of Computer Applications, 2019, 39(1): 87-92.
[13]	XU Yao, LI Zhuoran, MENG Jinlong, ZHAO Lipo, WEN Jianxin, WANG Guiling. Extraction method of marine lane boundary from exploiting trajectory big data [J]. Journal of Computer Applications, 2019, 39(1): 105-112.
[14]	TANG Xiaochuan, LUO Liang. Big data correlation mining algorithm based on factorial design [J]. Journal of Computer Applications, 2018, 38(9): 2507-2510.
[15]	CHEN Jingren, WU Yefu, WU Bing. Driver behavior spectrum analysis method based on vehicle driving data [J]. Journal of Computer Applications, 2018, 38(7): 1916-1922.