Large　data　generated　by　scientific　applications　imposes　challenges　in　storage　and　efficient　query　processing.　Many　queries　against　scientific　data　are　analytical　in　nature　and　require　super-linear　computation　time　using　straightforward　methods.　Spatial　distance　histogram　(SDH)　is　one　of　the　basic　queries　to　analyze　the　molecular　simulation　(MS)　data,　and　it　takes　quadratic　time　to　compute　using　brute-force　approach.　Often,　an　SDH　query　is　executed　continuously　to　analyze　the　simulation　system　over　a　period　of　time.　This　adds　to　the　total　time　required　to　compute　SDH.　In　this　paper,　we　propose　an　approximate　algorithm　to　compute　SDH　efficiently　over　consecutive　time　periods.　In　our　approach,　data　is　organized　into　a　Quad-tree　based　data　structure.　The　spatial　locality　of　the　particles　(at　given　time)　in　each　node　of　the　tree　is　acquired　to　determine　the　particle　distribution.　Similarly,　the　temporal　locality　of　particles　(between　consecutive　time　periods)　in　each　node　is　also　acquired.　The　spatial　distribution　and　temporal　locality　are　utilized　to　compute　the　approximate　SDH　at　every　time　instant.　The　performance　is　boosted　by　storing　and　updating　the　spatial　distribution　information　over　time.　The　efficiency　and　accuracy　of　the　proposed　algorithm　is　supported　by　mathematical　analysis　and　results　of　extensive　experiments　using　biological　data　generated　from　real　MS　studies.　©　2012　ACM.