An Effective Spatial Join Method for Blockchain-based Geospatial Data Using Hierarchical Quadrant Spatial LSM+ Tree

An Effective Spatial Join Method for Blockchain-based Geospatial Data Using Hierarchical Quadrant Spatial LSM+ Tree | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article An Effective Spatial Join Method for Blockchain-based Geospatial Data Using Hierarchical Quadrant Spatial LSM + Tree Junghyun Lee, Taehyeon Kwon, Sungwon Jung This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4015693/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 29 Apr, 2024 Read the published version in The Journal of Supercomputing → Version 1 posted 8 You are reading this latest preprint version Abstract The prevention of forgery and alternation of important data of blockchain technology is contributing widely to the expanding usage of this technology to areas and industries such as real estate and agriculture. Despite the high utilization of the blockchain, its write-intensive feature causes a large amount of disk I/Os when trying to index and process queries over the data. Among previous studies, the hierarchical quadrant spatial LSM tree (i.e., HQ-sLSM tree) was proposed as an effective structure to index large amounts of geospatial point data from the blockchainand process queries while triggering a low number of disk I/Os. However, geospatial data exists in forms such as lines and polygons inside cadastral maps and survey information. In this paper, we propose an extended version of the HQ-sLSM tree which indexes geospatial line and polygon data. The extended tree, named the HQ-sLSM+ tree inherits and adapts some common features and the low disk I/O algorithms of the original HQ-sLSM tree, fitting them to the line and polygon data types. Furthermore, an algorithm to process the spatial join query over two HQ-sLSM+ trees is proposed. A concept of a spatial join filter is introduced to access disk components efficiently. Experiments confirmed that the number of disk I/Os triggered when spatially joining two HQ-sLSM+ trees were much less compared to existing baseline index trees such as the R-tree and the LSM R-tree. Blockchain Hierarchical Quadrant Spatial LSM+ Tree HQ-sLSM Tree LSM Tree Spatial Filter Spatial Join Spatial Join Filter Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 29 Apr, 2024 Read the published version in The Journal of Supercomputing → Version 1 posted Editorial decision: Revision requested 26 Mar, 2024 Reviews received at journal 11 Mar, 2024 Reviewers agreed at journal 05 Mar, 2024 Reviewers agreed at journal 05 Mar, 2024 Reviewers invited by journal 05 Mar, 2024 Editor assigned by journal 05 Mar, 2024 Submission checks completed at journal 05 Mar, 2024 First submitted to journal 05 Mar, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4015693","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":276962568,"identity":"40145a00-7043-4adc-b31b-dae9a00ca811","order_by":0,"name":"Junghyun Lee","email":"","orcid":"","institution":"Sogang University","correspondingAuthor":false,"prefix":"","firstName":"Junghyun","middleName":"","lastName":"Lee","suffix":""},{"id":276962570,"identity":"1954948f-4059-4af7-b6a9-6b13d0ef3f01","order_by":1,"name":"Taehyeon Kwon","email":"","orcid":"","institution":"Sogang University","correspondingAuthor":false,"prefix":"","firstName":"Taehyeon","middleName":"","lastName":"Kwon","suffix":""},{"id":276962571,"identity":"f5f1e6a9-c72e-4336-b4f3-f703216e3623","order_by":2,"name":"Sungwon Jung","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA80lEQVRIiWNgGAWjYBACxgYogx9JkJk4LZINCEH8WuDA4ACxWphn5B5++bPtjt3m84cPv/i5o5aBv/0As3EFPofNyEuz5m17lrztRlqaZe+Z4wwSZxKYE8/g1ZJjZszYdjjZ7AaPmQFv2zEGhhsMzAcbCGgx/AnUYtx/xszwL1CLPBFajB/wth22M2DIMX7M21bDYADUkohXS88bM2aec4cTJIB+YZZtO8BjeCax2RCfFsP2HOOPP8oO2/P3Hz788W1bnZzc8cOHJfFqaWBgkwDSIKeAGId5kKIXO5AHRs0HIG3PAGHU4VU9CkbBKBgFIxMAAKi8UeD3g8GMAAAAAElFTkSuQmCC","orcid":"","institution":"Sogang University","correspondingAuthor":true,"prefix":"","firstName":"Sungwon","middleName":"","lastName":"Jung","suffix":""}],"badges":[],"createdAt":"2024-03-05 07:20:54","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4015693/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4015693/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s11227-024-06134-5","type":"published","date":"2024-04-29T23:27:28+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":55695029,"identity":"0cd104ca-c543-4dc4-a772-d7d7674fb0f0","added_by":"auto","created_at":"2024-05-02 00:55:33","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":2390903,"visible":true,"origin":"","legend":"","description":"","filename":"snarticletemplate240304.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4015693/v1_covered_d5f37895-405e-40cf-a608-022c1fc6b372.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"\u003cp\u003eAn Effective Spatial Join Method for Blockchain-based Geospatial Data Using Hierarchical Quadrant Spatial LSM\u003csup\u003e+\u003c/sup\u003e Tree\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"the-journal-of-supercomputing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [The Journal of Supercomputing](https://www.springer.com/journal/11227)","snPcode":"11227","submissionUrl":"https://submission.nature.com/new-submission/11227/3","title":"The Journal of Supercomputing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Blockchain, Hierarchical Quadrant Spatial LSM+ Tree, HQ-sLSM Tree, LSM Tree, Spatial Filter, Spatial Join, Spatial Join Filter","lastPublishedDoi":"10.21203/rs.3.rs-4015693/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4015693/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"The prevention of forgery and alternation of important data of blockchain technology is contributing widely to the expanding usage of this technology to areas and industries such as real estate and agriculture. Despite the high utilization of the blockchain, its write-intensive feature causes a large amount of disk I/Os when trying to index and process queries over the data. Among previous studies, the hierarchical quadrant spatial LSM tree (i.e., HQ-sLSM tree) was proposed as an effective structure to index large amounts of geospatial point data from the blockchainand process queries while triggering a low number of disk I/Os. However, geospatial data exists in forms such as lines and polygons inside cadastral maps and survey information. In this paper, we propose an extended version of the HQ-sLSM tree which indexes geospatial line and polygon data. The extended tree, named the HQ-sLSM+ tree inherits and adapts some common features and the low disk I/O algorithms of the original HQ-sLSM tree, fitting them to the line and polygon data types. Furthermore, an algorithm to process the spatial join query over two HQ-sLSM+ trees is proposed. A concept of a spatial join filter is introduced to access disk components efficiently. Experiments confirmed that the number of disk I/Os triggered when spatially joining two HQ-sLSM+ trees were much less compared to existing baseline index trees such as the R-tree and the LSM R-tree.","manuscriptTitle":"An Effective Spatial Join Method for Blockchain-based Geospatial Data Using Hierarchical Quadrant Spatial LSM+ Tree","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-03-08 10:48:33","doi":"10.21203/rs.3.rs-4015693/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-03-26T15:08:17+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-03-11T14:29:30+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"731da34f-5a05-4809-8ec1-b22e48b82d4d","date":"2024-03-06T02:35:43+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"cf5973d1-6066-44ae-a9c2-0d65490c004d","date":"2024-03-05T23:06:47+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-03-05T18:28:31+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-03-05T11:24:45+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-03-05T11:24:44+00:00","index":"","fulltext":""},{"type":"submitted","content":"The Journal of Supercomputing","date":"2024-03-05T07:19:10+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"the-journal-of-supercomputing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [The Journal of Supercomputing](https://www.springer.com/journal/11227)","snPcode":"11227","submissionUrl":"https://submission.nature.com/new-submission/11227/3","title":"The Journal of Supercomputing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"c074bf1d-674d-4b78-8383-9f1a32716ae0","owner":[],"postedDate":"March 8th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2024-05-01T23:27:29+00:00","versionOfRecord":{"articleIdentity":"rs-4015693","link":"https://doi.org/10.1007/s11227-024-06134-5","journal":{"identity":"the-journal-of-supercomputing","isVorOnly":false,"title":"The Journal of Supercomputing"},"publishedOn":"2024-04-29 23:27:28","publishedOnDateReadable":"April 29th, 2024"},"versionCreatedAt":"2024-03-08 10:48:33","video":"","vorDoi":"10.1007/s11227-024-06134-5","vorDoiUrl":"https://doi.org/10.1007/s11227-024-06134-5","workflowStages":[]},"version":"v1","identity":"rs-4015693","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4015693","identity":"rs-4015693","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}