Ευθύμης Δημόπουλος:

Γενικότερα πρόκειται για έναν αλγόριθμο που υπολογίζει τις αποστάσεις μεταξύ των παρατηρήσεων χρησιμοποιώντας π.χ. την Ευκλίδεια απόσταση

Υποθετωντας οτι χρησιμοποιεις χωροταξικα δεδομενα, υπαρχει ενα ενδεχομενο να χρησιμοποιησεις spatial data types τα οποια θα μπορεσουν να απλοποιησουν την προσεγγιση σου.
Αν τα δεδομενα σου ειναι σε 3D τοτε μαλλον θα πρεπει να φτιαξεις την δικη σου custom λυση εως οτου μια μελλοντικη εκδοση του SQL SERVER να προσφερει πραγματικη υποστηριξη σε 3D spatial data (ή εναλλακτικα να χρησιμοποιησεις αλλο db server που υποστηριζει 3D)

Σε ενα απο τα post αναφερεται:....ABS(y.a1-x.a1) CalcAttrA, ABS(y.a2-x.a2) CalcAttrB, ABS(y.a3-x.a3) CalcAttrC ....
οποτε υπαρχει η περιπτωση να "δουλευεις" με 3 διαφορετικα points in a 2D model.
Σε αυτην την περιπτωση μπορεις να ριξεις μια ματια στο παρακατω:

CREATE TABLE dbo.mypoints(ID INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
							point1 FLOAT,
							point2 FLOAT,
							point3 FLOAT,
							--spatial data
							gpoint1 geometry,
							gpoint2 geometry,
							gpoint3 geometry,
							_3dpoint geometry)
							
INSERT INTO dbo.mypoints(point1, point2, point3)
VALUES (8, 12, 6), (7, 23, 4), (15, 16, 17), (40, 1, 41)

--apply the geometry data
UPDATE dbo.mypoints
SET gpoint1 = 'POINT(' + CAST(point1 AS VARCHAR(50)) + ' 0)', --point on axis x
	gpoint2 = 'POINT(' + CAST(point2 AS VARCHAR(50)) + ' 0)', --point on axis x
	gpoint3 = 'POINT(' + CAST(point3 AS VARCHAR(50)) + ' 0)', --point on axis x
--3 dimensional point, however z axis is only informational :-(
_3dpoint = 'POINT(' + CAST(point1 AS VARCHAR(50)) + ' '+ CAST(point2 AS VARCHAR(50)) + ' '+ CAST(point31 AS VARCHAR(50)) + ' )' --0 SRID assumed, by default
	
	
	
-- create spatial indexes on x-axis points
CREATE SPATIAL INDEX idx_gpoint1 ON dbo.mypoints(gpoint1) WITH (BOUNDING_BOX = ( 0, 0, 100, 1 )) --adjust box upper x,y limits to include the possible max upper values on each axis in 2D
CREATE SPATIAL INDEX idx_gpoint2 ON dbo.mypoints(gpoint2) WITH (BOUNDING_BOX = ( 0, 0, 100, 1 ))
CREATE SPATIAL INDEX idx_gpoint3 ON dbo.mypoints(gpoint3) WITH (BOUNDING_BOX = ( 0, 0, 100, 1 ))


--get points on x axis that satisfy euclidean distance variables
DECLARE @_1pointdistance FLOAT,
		@_2pointdistance FLOAT,
		@_3pointdistance FLOAT

SELECT @_1pointdistance = 8, 
	@_2pointdistance = 10, 
	@_3pointdistance = 5


--get points based on distance per pair
SELECT a.id, b.id, 
		a.gpoint1.STAsText() AS a1_point, b.gpoint1.STAsText() AS b1_point, a.gpoint1.STDistance(b.gpoint1) AS firstpoint_distance, 
		a.gpoint2.STAsText() AS a2_point, b.gpoint2.STAsText() AS b2_point, a.gpoint2.STDistance(b.gpoint2) AS secondpoint_distance, 
		a.gpoint3.STAsText() AS a3_point, b.gpoint3.STAsText() AS b3_point, a.gpoint3.STDistance(b.gpoint3) AS thirdpoint_distance
FROM dbo.mypoints AS a
	JOIN dbo.mypoints AS b ON a.ID < b.ID
WHERE a.gpoint1.STDistance(b.gpoint1) > @_1pointdistance --spatial indexes optimize STDistance() calculations
  AND a.gpoint2.STDistance(b.gpoint2) > @_2pointdistance
  AND a.gpoint3.STDistance(b.gpoint3) > @_3pointdistance


--cleanup table
DROP TABLE dbo.mypoints	 

--ΗΤΗ--

Μιας και γίνεται λόγος για Ευκλείδια απόσταση, αν τα x,y,z είναι σημεία σε τρισδιάστατο χώρο, απ' όσο θυμάμαι από την αναλυτική γεωμετρία, ο σωστός τύπος είναι:

sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2)

Στο συγκεκριμένο thread, δίνονται δύο διαφορετικοί τύποι. Ο ένας είναι το άθροισμα των τετραγώνων των διαφορών και ο άλλος είναι το άθροισμα των απολύτων τιμών των διαφορών.

---

Ακόμα κι ένας άνθρωπος μπορεί ν' αλλάξει τον κόσμο. Μη θέλεις να κυβερνήσεις. Απλά δείξε το μονοπάτι κι ο κόσμος θ' ακολουθήσει!!

Markos:

Μιας και γίνεται λόγος για Ευκλείδια απόσταση, αν τα x,y,z είναι σημεία σε τρισδιάστατο χώρο, απ' όσο θυμάμαι από την αναλυτική γεωμετρία, ο σωστός τύπος είναι:

sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2)

Στο συγκεκριμένο thread, δίνονται δύο διαφορετικοί τύποι. Ο ένας είναι το άθροισμα των τετραγώνων των διαφορών και ο άλλος είναι το άθροισμα των απολύτων τιμών των διαφορών.

Μάρκο έχεις δίκιο απλά δεν ήθελα να δώσω έμφαση στους τύπους υπολογισμού (για να μην κουράσω). Ουσιαστικά ο ολοκληρωμένος τύπος καθώς και ο αλγόριθμος που θα χρησιμοποιήσω στην εφαρμογή μου είναι αρκετά πιο πολύπλοκος και πιστεύω πως μόλις τον ολοκληρώσω θα είμαι σε θέση να τον δημοσιεύσω



Απ'οτι κατάλαβα και νομίζω μου το επιβεβαιώνεται κι εσεις (?)  (και σύμφωνα και με δικές μου δοκιμές) είναι προτιμότερο να τρέχω on the fly ερώτημα το οποίο να υπολογίζει και να φιλτράρει ταυτόχρονα
απ' ότι αυτό που είχα αρχικά κατα νου: να κάνω τους υπολογισμούς, να τους αποθηκεύω και στη συνέχεια να τρέχω ερωτήματα τα οποία θα λαμβάνουν υπόψη τους τα thresholds και θα φιλτράρουν

από τις δοκιμές τις δικές μου έχω:
t1: 5000 rows
insert to t2: 12.497.500 rows ->10':15''
απλό select στο t2: 2':05''

select query without insertion (t2): 2':17''
με το order by : 2'56''

ΠΑΡΕΝΘΕΣΗ (σε τι μηχανήματα τα τρέχετε;;;;;;; πάω για αναβάθμιση... )

spaceman:

Υποθετωντας οτι χρησιμοποιεις χωροταξικα δεδομενα, υπαρχει ενα ενδεχομενο να χρησιμοποιησεις spatial data types τα οποια θα μπορεσουν να απλοποιησουν την προσεγγιση σου.
Αν τα δεδομενα σου ειναι σε 3D τοτε μαλλον θα πρεπει να φτιαξεις την δικη σου custom λυση εως οτου μια μελλοντικη εκδοση του SQL SERVER να προσφερει πραγματικη υποστηριξη σε 3D spatial data (ή εναλλακτικα να χρησιμοποιησεις αλλο db server που υποστηριζει 3D)

Σε ενα απο τα post αναφερεται:....ABS(y.a1-x.a1) CalcAttrA, ABS(y.a2-x.a2) CalcAttrB, ABS(y.a3-x.a3) CalcAttrC ....
οποτε υπαρχει η περιπτωση να "δουλευεις" με 3 διαφορετικα points in a 2D model.
Σε αυτην την περιπτωση μπορεις να ριξεις μια ματια στο παρακατω:

spaceman συγνώμη αλλά κάπου σε έχασα...

δεν αναφέρομαι σε χωροταξικά δεδομένα και κάπου μπερδεύτηκα... δεν μπορώ να κατανοήσω με μια πρόχειρη ματιά πως μπορώ να το ενσωματώσω στην εφαρμογή μου... θα το ξανακοιτάξω μόλις βρω λίγο χρόνο
σε ευχαριστώ για το post

Ευθύμης Δημόπουλος:

Απ'οτι κατάλαβα και νομίζω μου το επιβεβαιώνεται κι εσεις (?)  (και σύμφωνα και με δικές μου δοκιμές) είναι προτιμότερο να τρέχω on the fly ερώτημα το οποίο να υπολογίζει και να φιλτράρει ταυτόχρονα
απ' ότι αυτό που είχα αρχικά κατα νου: να κάνω τους υπολογισμούς, να τους αποθηκεύω και στη συνέχεια να τρέχω ερωτήματα τα οποία θα λαμβάνουν υπόψη τους τα thresholds και θα φιλτράρουν

Πάντα εξαρτάται από τι ακριβώς θες να κάνεις και γι αυτό σου είπαμε να εξηγήσεις την μεγαλύτερη εικόνα. Σε γενικές γραμμές η λύση του on-the-fly υπολογισμού και φιλτραρίσματος θα έχει μεγάλο κόστος σε CPU και μικρό σε I/O σε σχέση με τη λύση που έχεις κατά νου όπου συμβαίνει το ανάποδο. Το θέμα είναι όμως πόσους χρήστες θα έχεις που θα δουλεύουν ταυτόχρονα. Άν έχεις πολλούς που τρέχουν ταυτόχρονα τα queries της πρώτης λύσης μπορεί να έχεις θέμα με τα resources της CPU, αντίστοιχα με τη δεύτερη λύση θα έχεις θέμα με τα I/O resources. Από την άλλη, όλα θα γίνονται με queries; Μήπως θα υπάρχει εφαρμογή που θα μπορεί να βοηθήσει την κατάσταση; Πχ να κάνει η εφαρμογή τους υπολογισμούς και να cachάρει τα data;

 

---

Vir prudens non contra ventum mingit

KelMan:

Μήπως θα υπάρχει εφαρμογή που θα μπορεί να βοηθήσει την κατάσταση; Πχ να κάνει η εφαρμογή τους υπολογισμούς και να cachάρει τα data;

Θα υπάρχει εφαρμογή σε web forms με vb (έτσι ορίζουν τα specifications) γι' αυτο στην αρχή ανέφερα τα arraylists και τη λύση του programming με loops

Ευθύμης Δημόπουλος:

στο μυαλό μου φέρνω έναν τρόπο να γίνει με φόρτωμα του πίνακα σε arraylist και με programming-loops να γίνουν οι υπολογισμοί που θα αποθηκεύονται σε ένα νέο arraylist και στη συνέχεια
θα το αποθηκεύω σε sql table
όμως ανησυχώ :
-για τα resources που θα καταναλώνονται από άποψη μνήμης (μεγάλος όγκος δεδομένων)
-για την ταχύτητα
-για την ορθότητα του εγχειρήματος από άποψη ποιότητας κώδικα

κάποιος φίλος με παρέπεμψε να δω και τα cursors στον sql server, με τα οποία όμως δεν έχω ξανα-ασχοληθεί και δεν τα κατέχω (και μετά από googling) δεν έχω κάποια σαφή εικόνα στο μυαλό μου...

αλλά πιάσαμε να μιλάμε για sql solution οπότε θεώρησα αυτή σαν βέλτιστη λύση...

Ερώτηση:

Θεωρείς πως θα έχω καλύτερα αποτελέσματα όσον αφορά resources και ταχύτητα

1. αν φορτώσω τα data του αρχικού πίνακα σε κάποιο array
   
2. να κάνω τους υπολογισμούς μου με loops
   
3. στη συνέχεια να τα αποθηκεύσω στη μορφή του Β πίνακα
4. και εν συνεχεία να τα φιλτράρω με βάση τη προτίμηση του χρήστη
   
5. αποθηκεύοντας ή παρουσιάζοντας το τελικό αποτέλεσμα;
   

Κατά προτίμηση θα ήθελα -βελτιστοποιώντας την απόδοση της εφαρμογής να μοιράσω όσο δυνατόν τις λειτουργίες ώστε να μην επιβαρύνω πολύ το σύστημα

(ούτε να γονατίσω τον sql server, ούτε να ξεχειλώσω τη μνήμη και τη cpu)

Θα κάνω εγω το συνήγορο του γνωστού Δ...

Πιστεύει κανείς ότι θα φέρει ή θα δημιουργήσει έτσι εύκολα και με καλύτερο response 50.000.000 εγγραφές (και μιλάω για το μικρό δείγμα των 10.000 αρχικών εγγραφών) στον client ή θα τα έχει cached εκεί???

---

Antonios Chatzipavlis

Η προσέγγιση του trial and error είναι κακή στη δική σου περίπτωση εξαιτίας του μεγάλου όγκου των δεδομένων. Αν επρόκειτο για desktop εφαρμογή τρόπος αυτός θα ήταν υπό προϋπόθεση αποδεκτός, μιας και ένα άτομο μπορεί να περιμένει, να τροποποιεί τους περιορισμούς του προβλήματος και να ξαναδοκιμάζει. Ακόμα, όμως, και σ' αυτή την περίπτωση λείπει κάτι ουσιαστικό το οποίο λέγεται ανάλυση ευαισθησίας. Δεν είναι δυνατόν κάποιος να δοκιμάζει επ' άπειρον τις τιμές των ορίων των περιορισμών, μήπως και του "κάτσει" κάποια λύση. Σε περίπτωση που το πρόβλημα δεν λύνεται, πρέπει να παρέχεται η πληροφόρηση ως προς το ποια παράμετρος ευθύνεται και κατά πόσο πρέπει να τροποποιηθεί για να πάρει λύση.

Η προσέγγισή σου πρέπει ν' αλλάξει οπτική γωνία, ειδικά τώρα που πρόκειται για web εφαρμογή. Αντί ν' ασχολείσαι με τα points, ασχολήσου με τους περιορισμούς. Συνεργάσου με έναν μαθηματικό, έτσι ώστε να διατυπώσετε μια αναλυτική μεθοδολογία που θα σου φράσσει τα όρια της λύσης και μετά κάνε αναζήτηση ως προς εκείνα τα σημεία που πέφτουν "μέσα". Exhaustive search και υπολογισμός όλων των ενδιάμεσων αποτελεσμάτων είναι εγγύηση για αποτυχία.

---

Ακόμα κι ένας άνθρωπος μπορεί ν' αλλάξει τον κόσμο. Μη θέλεις να κυβερνήσεις. Απλά δείξε το μονοπάτι κι ο κόσμος θ' ακολουθήσει!!

Ευθύμης Δημόπουλος:

....και αν το count Χ των CalcAttrA, CalcAttrB,CalcAttrC που CalcAttrA>Τ2 κ.λπ. είναι μικρότερος του T3

Αν δεν ικανοποιούν τα αποτελέσματα τον χρήστη τότε εκείνος αλλάζει τις τιμές στα thresholds T1,T2,T3 και επαναλαμβάνει...

(δεν ήθελα να σας μπλέξω... αλλά... )

Κάτι που μπορεί να φανεί χρήσιμο είναι το γεγονός ότι το πλήθος των διαφορών (π.χ. CalcAttrA) πρέπει να είναι μικρότερο από ένα όριο, το Τ3. Αυτό σημαίνει ότι αν οι διαφορές είναι ν, το max πλήθος των σημείων είναι ν+1. Άρα θες ν+1<Τ3. Αυτό φωνάζει για χρήση γενετικών αλγορίθμων. Δημιουργείς έναν αρχικό πληθυσμό "χρωμοσωμάτων", όπου κάθε ένα τους θα περιέχει το πολύ ν+1 σημεία. Η επιλογή των σημείων θα γίνει με τρόπο τυχαίο. Μέσω διαδικασιών, "crossover", "mutation" και επιλογής, και με χρήση μιας συνάρτησης fitness που εσύ θα ορίσεις, θα δημιουργείς νέους πληθυσμούς όπου ο κάθε ένας θα προκύπτει από τον προηγούμενο. Η συνάρτηση fitness θα πρέπει να είναι κάποια "συνισταμένη" συνάρτηση των υπολοίπων περιορισμών που θέλεις να ικανοποιούνται. Όσο βελτιώνεται η τιμή της συνάρτησης fitness, τόσο πιο κοντά βρίσκεσαι στη λύση. Ύστερα από κάποιο πλήθος γενεών, επιλέγεις το χρωμόσωμα με την καλύτερη προσαρμογή και το παρουσιάζεις σαν λύση. Βέβαια, οι γενετικοί αλγόριθμοι δεν εξασφαλίζουν ούτε ότι θα ικανοποιούνται όλοι οι αρχικοί περιορισμοί, αλλά ούτε και ότι η λύση είναι η βέλτιστη. Επίσης, η επιτυχημένη εφαρμογή τους προϋποθέτει R&D, έτσι ώστε να εξασφαλιστεί ότι "δουλεύουν" με το συγκεκριμένο πρόβλημα. Είναι χρονοβόροι, αλλά μπροστά στο δικό σου exhaustive search... Όλ' αυτά βέβαια, αν το πρόβλημα δεν μπορεί να αντιμετωπιστεί με αναλυτικές μεθόδους. Just a thought...

---

Ακόμα κι ένας άνθρωπος μπορεί ν' αλλάξει τον κόσμο. Μη θέλεις να κυβερνήσεις. Απλά δείξε το μονοπάτι κι ο κόσμος θ' ακολουθήσει!!

Δεν ξέρω εάν το πρόβλημα έχει αλγεβρική λύση, αλλά σε περίπτωση  μπορούσες να κάνεις κάτι σε desktop χρησιμοποιώντας multi threading.

---

"When the darkness rises up from inside - that is normal.
It's when you reach down to pull it up - that the noxious warnings sound."
Tuzak, Farscape

Markos:

Η προσέγγιση του trial and error είναι κακή στη δική σου περίπτωση εξαιτίας του μεγάλου όγκου των δεδομένων. Αν επρόκειτο για desktop εφαρμογή τρόπος αυτός θα ήταν υπό προϋπόθεση αποδεκτός, μιας και ένα άτομο μπορεί να περιμένει, να τροποποιεί τους περιορισμούς του προβλήματος και να ξαναδοκιμάζει. Ακόμα, όμως, και σ' αυτή την περίπτωση λείπει κάτι ουσιαστικό το οποίο λέγεται ανάλυση ευαισθησίας. Δεν είναι δυνατόν κάποιος να δοκιμάζει επ' άπειρον τις τιμές των ορίων των περιορισμών, μήπως και του "κάτσει" κάποια λύση. Σε περίπτωση που το πρόβλημα δεν λύνεται, πρέπει να παρέχεται η πληροφόρηση ως προς το ποια παράμετρος ευθύνεται και κατά πόσο πρέπει να τροποποιηθεί για να πάρει λύση.

Η προσέγγισή σου πρέπει ν' αλλάξει οπτική γωνία, ειδικά τώρα που πρόκειται για web εφαρμογή. Αντί ν' ασχολείσαι με τα points, ασχολήσου με τους περιορισμούς. Συνεργάσου με έναν μαθηματικό, έτσι ώστε να διατυπώσετε μια αναλυτική μεθοδολογία που θα σου φράσσει τα όρια της λύσης και μετά κάνε αναζήτηση ως προς εκείνα τα σημεία που πέφτουν "μέσα". Exhaustive search και υπολογισμός όλων των ενδιάμεσων αποτελεσμάτων είναι εγγύηση για αποτυχία.

χμμ  σε αυτό που καταλήγω τελικά(?) είναι να περιορίσω το αρχικό δείγμα μου, μιας και τα παραγομένα αποτελέσματα θα αγγίζουν αστρονομικά νούμερα...

Αλήθεια γνωρίζει κανείς, σε τεχνικές data mining και σε αλγόριθμους για clustering όπως π.χ. η K-means, πόσα data είναι απαιτητό να "φορτώνονται";
Δηλαδή για ένα real world case study με πόσα data δουλεύει ο αλγόριθμος; (Μιλάω εμπειρικά πάντα..., ξέρω ότι μπορεί να υπάρχουν περιπτώσεις με 100 παρατηρήσεις και άλλα cases με 1Μ )

Ερώτηση: Τα αποτελέσματα θέλεις απλά να είναι υπολογισμένα βάση του αρχικού τραπεζιού, ή θέλεις να κάνεις τροποποίηση πάνω στα αποτελέσματα;

Εαν δεν σε ενδιαφέρει η τροποποίηση πάνω στα αποτελέσματα, η καλύτερη λύση είναι τα Views

Όλο τον υπολογισμό τον αναλαμβάνει η SQL, οπότε μπορείς να την εχει σε cluster η σε ο,τι θέλεις. Κάθε φορά που θα κάνεις μια νεα εγγραφή η SQL θα αναλαμβάνει να κανει update το "virtual" τραπέζι View. Τα δεδομένα αποθηκεύονται σαν να ηταν κανονικό τραπέζι και μπορείς να κάνεις query πάνω σε αυτά.

Και φυσικά μπορείς να έχεις παραπάνω απο 1 view, ανάλογα με τους υπολογισμούς που θέλεις να κάνεις.

edit: Απο performance μην το φοβάσαι, προσωπικά τρέχω σε cloud 8 επεξεργαστές sql, με ~1,5-2M εγγραφές το μήνα, και πολλαπλά indexed views, τα οποία όμως αποτελούνται μόνο απο joins και προσθέσεις (SUM() ) χωρίς κανένα απολύτως πρόβλημα

---

Αλλα τι νόημα έχουν όλα αυτά... Σύντομα έρχεται ο νιμπίρου.
www.egrapses.gr www.funnybook.gr

Μιχάλης